package stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author dx
 * @version 1.0
 * @date 2022/3/31 9:57
 * @description:  力扣 1475
 */
public class FinalPrices {

    public int[] finalPrices(int[] prices) {
        int len = prices.length;
        int [] ans = new int[len];
        Deque<Integer> stack = new LinkedList<Integer>();
        for(int i=len-1;i>=0;i--){

            while(stack.size()!=0 && stack.peek()>prices[i]){  //保证栈顶保留最近比当前price小的数
                stack.pop();
            }
            if(stack.size() == 0){
                ans[i] = prices[i]-0;
            }else{
                ans[i] = prices[i] - stack.peek();
            }
            stack.push(prices[i]);   //当前price的入栈,参与“保证栈顶保留最近比当前price小的数”
        }
        return ans;
    }
}
